// Problem 026: Reciprocal cycles
// A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
// 1/2	= 	0.5
// 1/3	= 	0.(3)
// 1/4	= 	0.25
// 1/5	= 	0.2
// 1/6	= 	0.1(6)
// 1/7	= 	0.(142857)
// 1/8	= 	0.125
// 1/9	= 	0.(1)
// 1/10	= 	0.1
// Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
// Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
// --------
// 1/n 的循环节长度的计算方法：
// 1）n 去除 2 和 5 的因子，记为 m，如 140 = 2*2*5*7 -> 7
// 2）循环节长度为 s，那么
// 1 / m = m / (10^s-1)
// 简言之，寻找 99999... 使其能够被 m 整除。

package main

import (
	"fmt"
	"math/big"
	"projecteuler/euler"
)

func p026() {
	max, n := 0, 0
	for x := 2; x < 1000; x++ {
		if l := lenOfRecurringCycle(x); l > max {
			max, n = l, x
		}
	}
	fmt.Println("Problem 026:", n)
}

func lenOfRecurringCycle(f int) int {
	ZERO := big.NewInt(0)
	TEN := big.NewInt(10)
	NINE := big.NewInt(9)
	f /= euler.GCD(320000, f) // remove divisors 2 and 5.
	t := big.NewInt(int64(f))
	m := big.NewInt(9)
	var z big.Int
	z.Mod(m, t)
	for z.Cmp(ZERO) != 0 {
		m.Mul(m, TEN).Add(m, NINE)
		z.Mod(m, t)
	}
	return len(m.String())
}
